public class BiTree {

    private class Node {
        int val;
        Node left;
        Node right;

        Node() {}
        Node(int val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
    }
    private Node root;

    public void insert(int val) {
        /**
         * 使用二叉查找树生成二叉树
         */
        Node node = new Node(val);
        if(this.root == null) {
            root = node;
        } else {
            Node current = root;
            Node parent;
            while(true) {
               parent = current;
               if(val < current.val) {
                   current = current.left;
                   if(current == null) {
                       parent.left = node;
                       return ;
                   }
               } else {
                   current = current.right;
                   if(current == null) {
                       parent.right = node;
                       return ;
                   }
               }
            }
        }
    }

    public boolean delete(int val) {
        Node current = this.root;
        Node parent = this.root;
        boolean isLeft = true;
        while(current.val != val) {
            parent = current;
            if(current.val > val) {
                current = current.left;
                isLeft = true;
            } else {
                current = current.right;
                isLeft = false;
            }
            if(current == null) {
                return false;
            }
        }
        if(current.left == null && current.right == null) {
            // 节点无子节点
            if(current == root) {
                this.root = null;
            } else if(isLeft) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        } else if(current.right == null) {
            // 节点无右节点
            if(current == root) {
                this.root = current.left;
            } else if(isLeft) {
                parent.left = current.left;
            } else {
                parent.right = current.left;
            }
        } else if(current.left == null) {
            // 节点无左节点
            if(current == root) {
                this.root = current.right;
            } else if(isLeft) {
                parent.left = current.right;
            } else {
                parent.right = current.right;
            }
        } else {
            // 节点有两个节点
            Node successor = this.getSuccessor(current);
            if(current == root) {
                root = successor;
            } else if(isLeft) {
                parent.left = successor;
            } else {
                parent.right = successor;
            }
            successor.left = current.left;
        }
        return true;
    }

    private Node getSuccessor(Node node) {
        /**
         *  寻找后继节点，即大于当前节点值的最小节点
         *  也即当前节点右子树的最左子树的节点
         */
        Node successorParent = node;
        Node successor = node;
        Node current = node.right;
        while(current != null) {
            successorParent = successor;
            successor = current;
            current = current.left;
        }
        if(successor != node.right) {
            successorParent.left = successor.right;   // 把后继节点的右子节点赋值给后继节点的父节点的左子节点
            successor.right = node.right;  // 把要删除节点的右子节点赋值给后继节点的右子节点 
        }
        return successor;
    }

    public void preTraverse(Node node) {
        // 先序遍历
        if(node != null) {
            System.out.printf("-%d-", node.val);
            this.preTraverse(node.left);
            this.preTraverse(node.right);
        }
    }

    public void midTraverse(Node node) {
        // 中序遍历
        if(node != null) {
            this.midTraverse(node.left);
            System.out.printf("-%d-", node.val);
            this.midTraverse(node.right);
        }
    }

    public void postTraverse(Node node) {
        // 后序遍历
        if(node != null) {
            this.postTraverse(node.left);
            this.postTraverse(node.right);
            System.out.printf("-%d-", node.val);
        }
    }

    public Node find(int val) {
        Node node = root;
        while(node.val != val) {
            if(node.val > val) {
                node = node.left;
            } else {
                node = node.right;
            }
            if(node == null) {
                return null;
            }
        }
        return node;
    }

    public static void main(String[] args) {
        int[] data = {5, 4, 3, 6, 8, 1, 2};
        BiTree tree = new BiTree();
        for(int i = 0; i < data.length; i ++) {
            tree.insert(data[i]);
        }
        tree.delete(3);
        tree.preTraverse(tree.root);
        System.out.println();
        tree.midTraverse(tree.root);
        System.out.println();
        tree.postTraverse(tree.root);
        System.out.println();
        System.out.println(tree.find(5));
    }
}
